红黑树 (RBT)
1.引入红黑树
可进行插入删除等系列操作,平衡二叉树在插入和删除时需要频繁的调整树形态,平衡二叉树以查为主,红黑树适合频繁插入、删除的场景。
红黑树左右高度差不会超过两倍。查找效率
2.红黑树的特点
首先是平衡二叉树. 然后引入结点颜色定义
- 结点是红或黑
- root是黑
- 叶子节点(NULL)都是黑
- 不存在两个连续的红结点
- 对每个结点,从该节点到任一叶结点的简单路径上,所含的黑结点的数目相同
注意红黑树中的叶结点是查找失败结点
3. 插入操作
新结点按照二叉排序树插入,并且是红色。然后判断是否影响红黑树定义。主要看是否破坏'不红红'特性
黑叔:
- LL: 右旋转,给原父节点和爷结点染色(黑红互换)
红叔:
- 叔父爷染色,爷当作新节点进一步处理